class Solution {
public:
    vector<int> res;
    void dfs(TreeNode* root,int sum){
      if(!root->left&&!root->right){
        res.push_back(sum);
        return;
      }
      if(root->left) dfs(root->left,sum+root->left->val);
      if(root->right) dfs(root->right,sum+root->right->val);   
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
      if(root == NULL) return false;
      dfs(root,root->val);
      for(int i = 0;i < res.size();i++){
        if(res[i] == targetSum){
          return true;
        }
      }
      return false;
    }
};
